Яндекс.Метрика — система интернет аналитики. Есть две Яндекс.Метрики — <a href='https://metrika.yandex.ru/'>Метрика для сайтов</a> и <a href='https://appmetrika.yandex.ru/'>Метрика для приложений</a>. На входе имеем поток данных — событий, происходящих на сайтах или в приложениях. Наша задача — обработать эти данные и представить их в подходящем для анализа виде.

Обработка данных — это не проблема. Проблема в том, как и в каком виде сохранять результаты обработки, чтобы с ними можно было удобно работать. Результатами работы Яндекс.Метрики, как правило, являются отчёты, которые отображаются в интерфейсе Метрики. То есть, вопрос — как хранить данные для отчётов.

<img src="https://habrastorage.org/files/e4e/c0f/8bc/e4ec0f8bc416435ba78565e68ca85b5f.png"/>

Яндекс.Метрика работает с 2008 года — более семи лет. За это время, нам приходилось несколько раз менять подход к хранению данных. Каждый раз это было обусловлено тем, что то или иное решение работало слишком плохо — с недостаточным запасом по производительности, недостаточно надёжно и с большим количеством проблем при эксплуатации, использовало слишком много вычислительных ресурсов, или же просто не позволяло нам реализовать то, что мы хотим.
<cut>
Рассмотрим, для получения какого конечного результата нам нужно сохранять данные.

В старой Метрике для сайтов, имеется около 40 «фиксированных» отчётов (например, отчёт по географии посетителей), несколько инструментов для in-page аналитики (например, карта кликов), Вебвизор (позволяет максимально подробно изучить действия отдельных посетителей) и, отдельно, конструктор отчётов.

В новой Метрике, а также в Метрике мобильных приложений, вместо «фиксированных» отчётов, каждый отчёт можно произвольным образом изменять — добавлять новые измерения (например, в отчёт по поисковым фразам добавить ещё разбиение по страницам входа на сайт), сегментировать и сравнивать (например, сравнить источники трафика на сайт для всех посетителей и посетителей из Москвы), менять набор метрик и т. п.

Конечно, это требует совершенно разных подходов к хранению данных. И сейчас мы их рассмотрим.

<h1>MyISAM</h1>

В самом начале Метрика создавалась, как часть Директа. В Директе для решения задачи хранения статистики использовались MyISAM таблицы, и мы тоже с этого начали. Мы использовали MyISAM для хранения «фиксированных» отчётов с 2008 по 2011 год. Рассмотрим, какой должна быть структура таблицы для отчёта. Например, для отчёта по географии.

Отчёт показывается для конкретного сайта (точнее, номера счётчика Метрики). Значит в первичный ключ должен входить номер счётчика — CounterID. Пользователь может выбрать для отчёта произвольный отчётный период (интервал дат — дату начала и дату конца). Сохранять данные для каждой пары дат было бы неразумно. Вместо этого, данные сохраняются для каждой даты и затем суммируются для заданного интервала дат, при запросе. То есть, в первичный ключ входит дата — Date.

В отчёте данные отображаются для регионов, в виде дерева из стран, областей, городов и т. п., либо в виде списка — например, списка городов. Разумно поместить в первичный ключ таблицы идентификатор региона (RegionID), а собирать данные в дерево уже на стороне прикладного кода а не базы данных.

Среди метрик считается, например, средняя продолжительность визита. Значит в столбцах таблицы должно быть количество визитов и суммарная продолжительность визитов.

В итоге, структура таблицы такая: CounterID, Date, RegionID -> Visits, SumVisitTime, …

Рассмотрим, что происходит, когда мы хотим получить отчёт. Делается запрос SELECT с условием <code>WHERE CounterID = c AND Date BETWEEN min_date AND max_date</code>. То есть, происходит чтение по диапазону первичного ключа.

<strong>Как реально хранятся данные на диске?</strong>

MyISAM таблица представляет собой файл с данными и файл с индексами. Если из таблицы ничего не удалялось, и строчки не изменяли своей длины при обновлении, то файл с данными представляет собой сериализованные строчки, уложенные подряд, в порядке их добавления. Индекс (в том числе, первичный ключ) представляет собой B-дерево, в листьях которого находятся смещения в файле с данными.

Когда мы читаем данные по диапазону индекса, из индекса достаётся множество смещений в файле с данными. Затем по этому множеству смещений делаются чтения из файла с данными.

Предположим естественную ситуацию, когда индекс находится в оперативке (key cache в MySQL или системный page cache), а данные не закэшированы в оперативке. Предположим, что мы используем жёсткие диски. Время для чтения данных зависит от того, какой объём данных нужно прочитать и сколько нужно сделать seek-ов. Количество seek-ов определяется локальностью расположения данных на диске.

События в Метрику поступают в порядке, почти соответствующим времени событий. В этом входящем потоке данных, данные разных счётчиков разбросаны совершенно произвольным образом. То есть, входящие данные локальны по времени, но не локальны по номеру счётчика. А значит, при записи в MyISAM таблицу, данные разных счётчиков будут так же расположены совершенно случайным образом.

А это значит, что для чтения данных отчёта, необходимо будет выполнить примерно столько случайных чтений, сколько есть нужных нам строк в таблице. Обычный жёсткий диск 7200 RPM умеет выполнять от 100 до 200 случайных чтений в секунду, RAID-массив, при грамотном использовании — пропорционально больше. Один SSD пятилетней давности умеет выполнять 30&nbsp;000 случайных чтений в секунду, но мы не можем позволить себе хранить наши данные на SSD.

Таким образом, если для нашего отчёта нужно прочитать 10&nbsp;000 строк, то это вряд ли займёт меньше 10 секунд, что полностью неприемлимо.

Для чтений по диапазону первичного ключа лучше подходит InnoDB, так как в InnoDB используется <a href='http://en.wikipedia.org/wiki/Database_index#Clustered'>кластерный первичный ключ</a> (то есть, данные хранятся упорядоченно по первичному ключу). Но InnoDB было невозможно использовать из-за низкой скорости записи. Если читая этот текст, вы вспомнили про <a href='http://www.tokutek.com/tokudb-for-mysql/'>TokuDB</a>, то продолжайте читать этот текст.

Для того, чтобы MyISAM работала быстрее при выборе по диапазону первичного ключа, применялись некоторые трюки.

Сортировка таблицы. Так как данные необходимо обновлять инкрементально, то один раз отсортировать таблицу недостаточно, а сортировать её каждый раз невозможно. Тем не менее, это можно делать периодически для старых данных.

Партиционирование. Таблица разбивается на некоторое количество более маленьких по диапазонам первичного ключа. При этом есть надежда, что данные одной партиции будут храниться более-менее локально, и запросы по диапазону первичного ключа будут работать быстрее. Этот метод можно называть «кластерный первичный ключ вручную». При этом, вставка данных несколько замедляется. Выбирая количество партиций, как правило, удаётся достичь компромисса между скоростью вставок и чтений.

Разделение данных на поколения. При одной схеме партиционирования, могут слишком тормозить чтения, при другой — вставки, а при промежуточной — и то, и другое. В этом случае возможно разделение данных на два — несколько поколений. Например, первое поколение назовём оперативными данными — там партиционирование производится в порядке вставки (по времени) или не производится вообще. Второе поколение назовём архивными данными — там партиционирование производится в порядке чтения (по номеру счётчика). Данные переносятся из поколения в поколение скриптом, не слишком часто (например, раз в день). Данные считываются сразу из всех поколений. Это, как правило, помогает, но добавляет довольно много сложностей.

Все эти трюки, и некоторые другие, использовались в Яндекс.Метрике когда-то давно для того, чтобы всё хоть как-то работало.

Резюмируем, какие имеются недостатки:
<ul>
<li>очень сложно поддерживать локальность данных на диске;</li>
<li>блокировка таблицы при записи данных;</li>
<li>медленно работает репликация, реплики зачастую отстают;</li>
<li>не обеспечивается консистентность данных после сбоя;</li>
<li>очень сложно рассчитывать и хранить сложные агрегаты, такие как количество уникальных посетителей;</li>
<li>затруднительно использовать сжатие данных; сжатие данных работает неэффективно;</li>
<li>индексы занимают много места и зачастую не помещаются в оперативку;</li>
<li>необходимость шардировать данные вручную;</li>
<li>много вычислений приходится делать на стороне прикладного кода, после SELECT-а;</li>
<li>сложность эксплуатации.</li>
</ul>

<img src="https://habrastorage.org/files/7a9/757/7e3/7a97577e332d44ed8fab1b2613dd647e.png"/>

<em>Локальность данных на диске, образное представление</em>

В целом, использование MyISAM было крайне неудобным. В дневное время серверы работали со 100% нагрузкой на дисковые массивы (постоянное перемещение головок). При такой нагрузке, диски выходят из строя чаще, чем обычно. На серверах мы использовали дисковые полки (16 дисков) — то есть, довольно часто приходилось восстанваливать RAID-массивы. При этом, репликация отстаёт ещё больше и иногда реплику приходится наливать заново. Переключение мастера крайне неудобно. Для выбора реплики, на которую отправляются запросы, мы использовали MySQL Proxy, и это использование было весьма неудачным (потом заменили на HAProxy).

Несмотря на эти недостатки, по состоянию на 2011 год, мы хранили в MyISAM таблицах более 580 миллиардов строк. Потом всё переконвертировали в Metrage, удалили и в итоге освободили много серверов.


<h1>Metrage</h1>

Название Metrage (или по-русски — «Метраж») происходит от слов «Метрика» и «Агрегированные данные». Мы используем Metrage для хранения фиксированных отчётов с 2010 года по настоящее время.

Предположим, имеется следующий сценарий работы:
<ul>
<li>данные постоянно записываются в базу, небольшими batch-ами;</li>
<li>поток на запись сравнительно большой — несколько сотен тысяч строк в секунду;</li>
<li>запросов на чтение сравнительно мало — десятки-сотни запросов в секунду;</li>
<li>все чтения — по диапазону первичного ключа, до миллионов строк на один запрос;</li>
<li>строчки достаточно короткие — около 100 байт в несжатом виде.</li>
</ul>
Для такого сценария работы хорошо подходит структура данных <a href='http://en.wikipedia.org/wiki/Log-structured_merge-tree'>LSM-Tree</a>.

LSM-Tree представляет собой сравнительно небольшой набор «кусков» данных на диске. Каждый кусок содержит данные, отсортированные по первичному ключу. Новые данные сначала располагаются в какой либо структуре данных в оперативке (MemTable), затем записываются на диск в новый сортированный кусок. Периодически, в фоне, несколько сортированных кусков объединяются в один более крупный сортированный кусок (compaction). Таким образом, постоянно поддерживается сравнительно небольшой набор кусков.

LSM-Tree — достаточно распространённая структура данных.
Среди встраиваемых структур данных, LSM-Tree реализуют <a href='https://github.com/google/leveldb'>LevelDB</a>, <a href='http://rocksdb.org/'>RocksDB</a>.
LSM-Tree используется в <a href='http://hbase.apache.org/'>HBase</a> и <a href='http://cassandra.apache.org/'>Cassandra</a>.

<img src="https://habrastorage.org/files/826/43d/3f9/82643d3f92324e2498f43a82d2200485.png"/>
<em>Схема работы LSM-Tree</em>

Метраж также представляет собой LSM-Tree. В качестве «строчек» в Метраже могут использоваться произвольные структуры данных (фиксированы на этапе компиляции). Каждая строчка — это пара ключ, значение. Ключ представляет собой структуру с операциями сравнения на равенство и неравенство. Значение — произвольная структура с операциями update (добавить что-нибудь) и merge (агрегировать — объединить с другим значением). Короче говоря, значения представляют собой <a href='http://en.wikipedia.org/wiki/Conflict-free_replicated_data_type'>CRDT</a>.

В качестве значений могут выступать как простые структуры (кортеж чисел), так и более сложные (хэш-таблица для рассчёта количества уникальных посетителей, структура для карты кликов).

С помощью операций update и merge, постоянно выполняется инкрементальная агрегация данных:
<ul>
<li>во время вставки данных, при формировании новой пачки в оперативке;</li>
<li>во время фоновых слияний;</li>
<li>при запросах на чтение;</li>
</ul>
Также Метраж содержит нужную нам domain-specific логику, которая выполняется при запросах. Например, для отчёта по регионам, ключ в таблице будет содержать идентификатор самого нижнего региона (город, посёлок), и если нам нужно получить отчёт по странам, то доагрегация данных в данные по странам будет произведена на стороне сервера БД.

Рассмотрим достоинства этой структуры данных:

Данные расположены достаточно локально на жёстком диске, чтения по диапазону работают быстро.

Данные сжимаются по блокам. За счёт хранения в упорядоченном виде, сжатие достаточно сильное при использовании быстрых алгоритмов сжатия (в 2010 году использовали <a href='http://www.quicklz.com/'>QuickLZ</a>, с 2011 используем <a href='http://fastcompression.blogspot.ru/p/lz4.html'>LZ4</a>).

Хранение данных в упорядоченном виде позволяет использовать разреженный индекс. Разреженный индекс — это массив значений первичного ключа для каждой N-ой строки (N порядка тысяч). Такой индекс получается максимально компактным и всегда помещается в оперативку.

Так как чтения выполняются не очень часто, но при этом читают достаточно много строк, то увеличение latency из-за наличия многих кусков, из-за необходимости разжатия блока данных, и чтение лишних строк из-за разреженности индекса, не имеют значения.

Записанные куски данных не модифицируются. Это позволяет производить чтение и запись без блокировок — для чтения берётся снепшот данных.

Используется простой и единообразный код, но при этом мы можем легко реализовать всю нужную нам domain-specific логику.

Нам пришлось написать Метраж вместо доработки какого-либо существующего решения, потому что какого-либо существующего решения не было. Например, LevelDB не существовала в 2010 году. TokuDB в то время была доступна только за деньги. Все существовавшие системы, реализующие LSM-Tree подходят для хранения неструктурированных данных — отображения типа BLOB -> BLOB, с небольшими вариациями. Для того, чтобы адаптировать такую систему для работы с произвольными CRDT, потребовалось бы гораздо больше времени, чем на разработку Метража.

Конвертация данных из MySQL в Метраж была достаточно трудоёмкой: чистое время на работу программы конвертации — всего лишь около недели, но выполнить основную часть работы удалось только за два месяца. После перевода отчётов на Метраж, мы сразу же получили преимущество в скорости работы интерфейса Метрики. Так, 90% перцентиль времени загрузки отчёта по заголовкам страниц уменьшился с 26 секунд до 0.8 секунд (общее время, включая работу всех запросов к базам данных и последующих преобразований данных). Время обработки запросов самим Метражом (для всех отчётов) составляет: медиана — 6&nbsp;мс, 90% — 31&nbsp;мс, 99% — 334&nbsp;мс.

По опыту эксплуатации в течение пяти лет, Метраж показал себя как надёжное, беспроблемное решение. За всё время было всего лишь несколько незначительных сбоев. Преимущества в эффективности и в простоте использования, по сравнению с хранением данных в MyISAM, являются кардинальными.

Сейчас мы храним в Метраже 3.37 триллиона строк. Для этого используется 39 * 2 серверов. Мы постепенно отказываемся от хранения данных в Метраже и уже удалили несколько наиболее крупных таблиц. Недостаток Метража — возможность эффективной работы только с фиксированными отчётами. Метраж выполняет агрегацию данных и хранит агрегированные данные. А для того, чтобы это делать, нужно заранее перечислить все способы, которыми мы хотим агрегировать данные. Если мы будем агрегировать данные 40 разными способами — значит в Метрике будет 40 отчётов, но не больше.


<h1>OLAPServer</h1>

В Яндекс.Метрике, объём данных и величина нагрузки являются достаточно большими, чтобы основной проблемой было сделать решение, которое хотя бы работает — решает задачу и при этом справляется с нагрузкой в рамках адекватного количества вычислительных ресурсов. Поэтому, зачастую, основные усилия тратятся на то, чтобы сделать минимальный работающий прототип.

Одним из таких прототипов был OLAPServer. Мы использовали OLAPServer с 2009 по 2013 год в качестве структуры данных для конструктора отчётов.

Задача — получать произвольные отчёты, структура которых становится известна лишь в момент, когда пользователь хочет получить отчёт. Для этой задачи невозможно использовать предагрегированные данные, потому что невозможно предусмотреть заранее все комбинации измерений, метрик, условий. А значит, нужно хранить неагрегированные данные. Например, для отчётов, вычисляемых на основе визитов, необходимо иметь таблицу, где каждому визиту будет соответствовать строчка, а каждому параметру, по которому можно рассчитать отчёт, будет соответствовать столбец.

Имеем такой сценарий работы:
<ul>
<li>есть широкая «<a href='http://en.wikipedia.org/wiki/Fact_table'>таблица фактов</a>», содержащая большое количество столбцов (сотни);</li>
<li>при чтении, вынимается достаточно большое количество строк из БД, но только небольшое подмножество столбцов;</li>
<li>запросы на чтение идут сравнительно редко (обычно не более сотни в секунду на сервер);</li>
<li>при выполнении простых запросов, допустимы задержки в районе 50&nbsp;мс;</li>
<li>значения в столбцах достаточно мелкие — числа и небольшие строки (пример — 60 байт на URL);</li>
<li>требуется высокая пропускная способность при обработке одного запроса (до миллиардов строк в секунду на один сервер);</li>
<li>результат выполнения запроса существенно меньше исходных данных — то есть, данные фильтруются или агрегируются;</li>
<li>сравнительно простой сценарий обновления данных, обычно append-only batch-ами; нет сложных транзакций.</li>
</ul>
Для такого сценария работы (назовём его <a href='http://en.wikipedia.org/wiki/Online_analytical_processing'>OLAP</a> сценарий работы), наилучшим образом подходят столбцовые СУБД <a href='(http://en.wikipedia.org/wiki/Column-oriented_DBMS'>column-oriented DBMS</a>). Так называются СУБД, в которых данные для каждого столбца хранятся отдельно, а данные одного столбца — вместе.

Столбцовые СУБД эффективно работают для OLAP сценария работы по следующим причинам:

1. По I/O.
1.1. Для выполнения аналитического запроса, требуется прочитать небольшое количество столбцов таблицы. В столбцовой БД для этого можно читать только нужные данные. Например, если вам требуется только 5 столбцов из 100, то следует рассчитывать на 20-кратное уменьшение ввода-вывода.
1.2. Так как данные читаются пачками, то их проще сжимать. Данные, лежащие по столбцам также лучше сжимаются. За счёт этого, дополнительно уменьшается объём ввода-вывода.
1.3. За счёт уменьшения ввода-вывода, больше данных влезает в системный кэш.

Для примера, для запроса «посчитать количество записей для каждой рекламной системы», требуется прочитать один столбец «идентификатор рекламной системы», который занимает 1 байт в несжатом виде. Если большинство переходов было не с рекламных систем, то можно рассчитывать хотя бы на десятикратное сжатие этого столбца. При использовании быстрого алгоритма сжатия, возможно разжатие данных со скоростью более нескольких гигабайт несжатых данных в секунду. То есть, такой запрос может выполняться со скоростью около нескольких миллиардов строк в секунду на одном сервере.

2. По CPU.
Так как для выполнения запроса надо обработать достаточно большое количество строк, становится актуальным диспетчеризовывать все операции не для отдельных строк, а для целых векторов (пример — векторный движок в СУБД <a href='http://sites.computer.org/debull/A12mar/vectorwise.pdf'>VectorWise</a>), или реализовать движок выполнения запроса так, чтобы издержки на диспетчеризацию были примерно нулевыми (пример — кодогенерация с помощью <a href='http://blog.cloudera.com/blog/2013/02/inside-cloudera-impala-runtime-code-generation/'>LLVM в Cloudera Impala</a>). Если этого не делать, то при любой не слишком плохой дисковой подсистеме, интерпретатор запроса неизбежно упрётся в CPU. Имеет смысл не только хранить данные по столбцам, но и обрабатывать их, по возможности, тоже по столбцам.

<img src="https://habrastorage.org/files/2eb/c3e/79e/2ebc3e79e506499098bafb4ff59603c3.gif"/>
<em>Получение отчёта из столбцовой базы данных</em>

Существует достаточно много столбцовых СУБД. Это, например, <a href='http://www.vertica.com/'>Vertica</a>, Paraccel <a href='(http://www.actian.com/products/analytics-platform/matrix-mpp-analytics-database/'>Actian Matrix</a>) <a href='(http://aws.amazon.com/redshift/'>Amazon Redshift</a>), Sybase IQ (SAP IQ), <a href='http://www.exasol.com/en/'>Exasol</a>, <a href='https://www.infobright.com/'>Infobright</a>, <a href='https://github.com/infinidb/infinidb'>InfiniDB</a>, <a href='https://www.monetdb.org/Home'>MonetDB</a> (VectorWise) <a href='(http://www.actian.com/products/analytics-platform/vector-smp-analytics-database/'>Actian Vector</a>), <a href='http://luciddb.sourceforge.net/'>LucidDB</a>, <a href='http://hana.sap.com/abouthana.html'>SAP HANA</a>, <a href='http://research.google.com/pubs/pub36632.html'>Google Dremel</a>, <a href='http://vldb.org/pvldb/vol5/p1436_alexanderhall_vldb2012.pdf'>Google PowerDrill</a>, <a href='http://druid.io/'>Metamarkets Druid</a>, <a href='http://kx.com/software.php'>kdb+</a> и т. п.

В традиционно строковых СУБД последнее время тоже стали появляться решения для хранения данных по столбцам. Примеры — column store index в <a href='https://msdn.microsoft.com/en-us/gg492088.aspx'>MS SQL Server</a>, <a href='http://docs.memsql.com/latest/concepts/columnar/'>MemSQL</a>; <a href='https://github.com/citusdata/cstore_fdw'>cstore_fdw</a> для Postgres, форматы ORC-File и <a href='http://parquet.apache.org/'>Parquet</a> для Hadoop.

OLAPServer представляет собой простейшую и крайне ограниченную реализацию столбцовой базы данных. Так, OLAPServer поддерживает всего лишь одну таблицу, заданную в compile time — таблицу визитов. Обновление данных делается не в реальном времени, как везде в Метрике, а несколько раз в сутки. В качестве типов данных поддерживаются только числа фиксированной длины 1-8 байт. А в качестве запроса поддерживается лишь вариант <code>SELECT keys..., aggregates... FROM table WHERE condition1 AND condition2 AND... GROUP BY keys ORDER BY column_nums...</code>

Несмотря на такую ограниченную функциональность, OLAPServer успешно справлялся с задачей конструктора отчётов. Но не справлялся с задачей — реализовать возможность кастомизации каждого отчёта Яндекс.Метрики. Например, если отчёт содержал URL-ы, то его нельзя было получить через конструктор отчётов, потому что OLAPServer не хранил URL-ы; не удавалось реализовать часто необходимую нашим пользователям функциональность — просмотр страниц входа для поисковых фраз.

По состоянию на 2013 год, мы хранили в OLAPServer 728 миллиардов строк. Потом все данные переложили в ClickHouse и удалили.


<h1>ClickHouse</h1>

Используя OLAPServer, мы успели понять, насколько хорошо столбцовые СУБД справляются с задачей ad-hoc аналитики по неагрегированным данным. Если любой отчёт можно получить по неагрегированным данным, то возникает вопрос, нужно ли, вообще, предагрегировать данные заранее, как мы это делаем, используя Metrage?

С одной стороны, предагрегация данных позволяет уменьшить объём данных, используемых непосредственно в момент загрузки страницы с отчётом.
Но агрегированные данные являются очень ограниченным решением, по следующим причинам:
<ul>
<li>вы должны заранее знать перечень отчётов, необходимых пользователю;</li>
<li>то есть, пользователь не может построить произвольный отчёт;</li>
<li>при агрегации по большому количествую ключей, объём данных не уменьшается и агрегация бесполезна;</li>
<li>при большом количестве отчётов, получается слишком много вариантов агрегации (комбинаторный взрыв);</li>
<li>при агрегации по ключам высокой кардинальности (например, URL) объём данных уменьшается не сильно (менее чем в 2 раза);</li>
<li>из-за этого, объём данных при агрегации может не уменьшиться, а вырасти;</li>
<li>пользователи будут смотреть не все отчёты, которые мы для них посчитаем — то есть, большая часть вычислений бесполезна;</li>
<li>сложно поддерживать логическую целостность при хранении большого количества разных агрегаций;</li>
</ul>
Как видно, если ничего не агрегировать, и работать с неагрегированными данными, то это даже может уменьшить объём вычислений.
Но если работать только с неагрегированными данными, то это накладывает очень высокие требования к эффективности работы той системы, которая будет выполнять запросы.

Так, если мы агрегируем данные заранее, то мы это делаем, хоть и постоянно (в реальном времени), но зато асинхронно по отношению к пользовательским запросам. Мы должны всего лишь успевать агрегировать данные в реальном времени, а на момент получения отчёта, используются уже, по большей части, подготовленные данные.

А если не агрегировать данные заранее, то всю работу нужно делать в момент запроса пользователя — пока пользователь ждёт загрузки страницы с отчётом. Это значит, что нам может потребоваться, во время запроса, обработать многие миллиарды строк, и чем быстрее — тем лучше.

Для этого нужна хорошая столбцовая СУБД. На рынке не существует ни одной столбцовой СУБД, которая могла бы достаточно хорошо работать на задачах интернет-аналитики масштаба рунета, и при этом имела бы не запретительно высокую стоимость лицензий. Если бы мы использовали некоторые из решений, перечисленных в предыдущем разделе, то стоимость лицензий многократно превысила бы стоимость всех наших серверов и сотрудников.

В качестве альтернативы коммерческим столбцовым СУБД, последнее время стали появляться решения для эффективной ad-hoc аналитики по данным, находящимся в системах распределённых вычислений: <a href='http://impala.io/'>Cloudera Impala</a>, <a href='https://spark.apache.org/sql/'>Spark SQL</a>, <a href='https://www.facebook.com/notes/facebook-engineering/presto-interacting-with-petabytes-of-data-at-facebook/10151786197628920'>Presto</a>, <a href='http://drill.apache.org/'>Apache Drill</a>. Хотя такие системы могут эффективно работать на запросах для внутренних аналитических задач, достаточно трудно представить их в качестве бэкенда для веб-интерфейса аналитической системы, доступной внешним пользователям.

В Яндексе разработана своя столбцовая СУБД — ClickHouse. Рассмотрим основные преимущества ClickHouse.

<strong>ClickHouse подходит для больших данных</strong>

В новой Яндекс.Метрике ClickHouse используется для хранения всех данных для отчётов. Объём базы данных (декабрь 2015) составляет 11.4 триллионов строк (только для большой Метрики). Строчки — неагрегированные данные, которые используются для получения отчётов в реальном времени. Каждая строчка в наиболее крупных таблицах содержит более 200 столбцов.

<strong>ClickHouse линейно масштабируется</strong>

ClickHouse позволяет увеличивать размер кластера путём добавления новых серверов по мере необходимости. Для примера, основной кластер Яндекс.Метрики был увеличен с 60 до 394 серверов в течение двух лет. Для отказоустойчивости, серверы располагаются в разных датацентрах. ClickHouse может использовать все возможности железа для обработки одного запроса. Так достигается скорость более 1 терабайта в секунду (данных после разжатия, только используемые столбцы).

<strong>ClickHouse быстро работает</strong>

Высокая производительность ClickHouse является нашим отдельным предметом гордости. По результатам тестов, ClickHouse обрабатывает запросы быстрее, чем любая другая система, которую мы могли достать. Для примера, ClickHouse в среднем в 2.8 — 3.4 раза быстрее, чем Vertica. В ClickHouse нет одной серебрянной пули, за счёт которой система работает так быстро. Производительность — это результат систематической работы, которую мы постоянно делаем.

<strong>ClickHouse обладает богатой функциональностью</strong>

ClickHouse поддерживает диалект языка SQL. Поддерживаются подзапросы и JOIN-ы (локальные и распределённые).
Присутствуют многочисленные расширения SQL: функции для веб-аналитики, массивы и вложенные структуры данных, функции высшего порядка, агрегатные функции для приближённых вычислений с помощью sketching и т. п. При работе с ClickHouse вы получаете удобство реляционной СУБД.

<strong>ClickHouse прост в использовании</strong>

Не смотря на то, что ClickHouse — внутренняя разработка, мы сделали так, что ClickHouse похож на коробочный продукт, который легко устанавливается по инструкции и работает сразу. Хотя ClickHouse способен работать на кластерах большого размера, система может быть установлена на один сервер или даже на виртуальную машину.

ClickHouse разработан в команде Яндекс.Метрики. При этом, систему удалось сделать достаточно гибкой и расширяемой для того, чтобы она могла успешно использоваться для разных задач. Сейчас имеется более десятка применений ClickHouse внутри компании.

ClickHouse хорошо подходит для создания всевозможных аналитических инструментов. Действительно, если ClickHouse успешно справляется с задачами большой Яндекс.Метрики, то можно быть уверенным, что с другими задачами ClickHouse справится с многократным запасом по производительности.

В этом смысле особенно повезло Метрике мобильных приложений — когда она находилась в разработке в конце 2013 года, ClickHouse уже был готов. Для обработки данных Метрики приложений, мы просто сделали одну программу, которая берёт входящие данные, и после небольшой обработки, записывает их в ClickHouse. Любая функциональность, доступная в интерфейсе Метрики приложений представляет собой просто запрос SELECT.

ClickHouse используется для хранения и анализа логов различных сервисов в Яндексе. Типичным решением было бы использовать Logstash и ElasticSearch, но оно не работает на более-менее приличном потоке данных.

ClickHouse подходит в качестве базы данных для временных рядов — так, в Яндексе ClickHouse используется в качестве бэкенда для <a href='http://graphite.wikidot.com/'>Graphite</a> вместо Ceres/Whisper — это позволяет работать более чем с триллионом метрик на одном сервере.

ClickHouse используют аналитики для внутренних задач. По приблизительной оценке, эффективность работы ClickHouse по сравнению с традиционными методами обработки данных (скрипты на MR) выше примерно на три порядка. Это нельзя рассматривать как просто количественное отличие. Дело в том, что имея такую высокую скорость расчёта, можно позволить себе принципиально другие методы решения задач.

Если аналитик получил задачу — сделать отчёт, и если это хороший аналитик, то он не будет делать один отчёт. Вместо этого, он сначала получит десяток других отчётов, чтобы лучше изучить природу данных, и проверять возникающие при этом гипотезы. Зачастую имеет смысл смотреть на данные под разными углами, даже не имея при этом какой либо чёткой цели - для того, чтобы находить новые гипотезы и проверять их.

Это возможно лишь если скорость анализа данных позволяет проводить исследования в интерактивном режиме. Чем быстрее выполняются запросы, тем больше гипотез можно проверить. При работе с ClickHouse возникает такое ощущение, как будто у вас увеличилась скорость мышления.

В традиционных системах, данные, образно выражаясь, лежат мёртвым грузом на дне болота. С ними можно сделать что угодно, но это займёт много времени и будет очень неудобно. А если ваши данные лежат в ClickHouse, то это «живые» данные: вы можете изучать их в любых срезах и «сверлить» до каждой отдельной строчки.


<h1>Выводы</h1>

Так уж получилось, что Яндекс.Метрика <a href='http://w3techs.com/technologies/overview/traffic_analysis/all'>является</a> второй по величине системой веб-аналитики в мире. Объём поступающих в Метрику данных вырос с 200 млн. событий в сутки в начале 2009 года до чуть более 20 млрд. в 2015 году. Чтобы дать пользователям достаточно богатые возможности, но при этом не перестать работать под возрастающей нагрузкой, нам приходилось постоянно менять подход к организации хранения данных.

Для нас очень важна эффективность использования железа. По нашему опыту, при большом объёме данных, стоит беспокоиться не о том, насколько система хорошо масштабируется, а о том, насколько эффективно используется каждая единица ресурсов: каждое процессорное ядро, диск и SSD, оперативка, сеть. Ведь если ваша система уже использует сотни серверов, а вам нужно работать в десять раз эффективнее, то вряд ли вы сможете легко установить тысячи серверов, как бы хорошо система не масштабировалась.

Для достижения маскимальной эффективности важна специализация под конкретный класс задач. Не существует структуры данных, которая хорошо справляется с совершенно разными сценариями работы. Например очевидно, что key-value база не подойдёт для аналитических запросов. Чем больше нагрузка на систему, тем большая специализация будет требоваться, и не стоит бояться использовать для разных задач принципиально разные структуры данных.

Нам удалось сделать так, что Яндекс.Метрика является относительно дешёвой по железу. Это позволяет предоставлять сервис даже для самых крупных сайтов и мобильных приложений. На этом поле, у Яндекс.Метрики нет конкурентов. Для примера, если у вас есть популярное мобильное приложение, то вы можете бесплатно использовать <a href='https://appmetrika.yandex.ru/'>Яндекс.Метрику для приложений</a>, даже если ваше приложение популярнее, чем Яндекс.Карты.
